/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年12月16日
*   描    述：
*   
================================================================*/


#include <iostream>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if( head == NULL || head->next == NULL )
            return head;
        
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = NULL;

        while( fast && fast->next ){
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }

        pre->next = NULL;

        ListNode* l = sortList(head);
        ListNode* r = sortList(slow);

        return merge(l, r);

    }

private:
    ListNode* merge(ListNode* left, ListNode* right){
        ListNode newhead = ListNode(0);
        ListNode *p = &newhead;

        while( left && right ){
            if( left->val < right->val ){
                p->next = left;
                p = p->next;
                left = left->next;
            } else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        
        p->next = left ? left:right; 

        return newhead.next;
    }

};
